1049. 最后一块石头的重量 II

Similar Question

Solution Tips

方案一: 01 背包问题

本题其实就是尽量让石头分成重量相同的两堆，相撞之后剩下的石头最小，这样就化解成 01 背包问题了。

是不是感觉和昨天讲解的 416. 分割等和子集 (opens new window) 非常像了。

var lastStoneWeightII = function (stones) {
    let sum = stones.reduce((s, n) => s + n);

    let dpLen = Math.floor(sum / 2);
    let dp = new Array(dpLen + 1).fill(0);

    for (let i = 0; i < stones.length; ++i) {
        for (let j = dpLen; j >= stones[i]; --j) {
            dp[j] = Math.max(dp[j], dp[j - stones[i]] + stones[i]);
        }
    }

    return sum - dp[dpLen] - dp[dpLen];
};